package com.cat.dynamicPlanning02;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/beautiful-arrangement/
 * @create 2025/9/12 20:20
 * @since JDK17
 */

public class Solution06 {
    int[] dp, arr;
    int n, ans;
    void f(int status, int cur) {
        if (cur == n + 1) {
            ans++;
        }
        for (int i = 1; i <= n; i++) {
            if ((status & 1 << i) != 0 && (i % cur == 0 || cur % i == 0)) {
                f(status ^ 1 << i, cur + 1);
            }
        }
    }


    public int countArrangement(int n) {
        dp = new int[1 << n + 1];
        arr = new int[n + 1];
        this.n = n;
        f((1 << n + 1) - 1, 1);
        return ans;
    }
}
